1. Technical Field
The invention relates generally to content addressable memory (CAM ) devices, and more specifically, to the design and use of Match-Detecting Match Line Controller circuitry for CAMs.
2. Related Art
A Content Addressable Memory (CAM) is a device adapted to perform fast (e.g., single-clock cycle) searches of list based data stored in a plurality of locations called entries.
As depicted in FIG. 1, a CAM cell 101 differs from a Random Access Memory (RAM) storage cell in that a CAM cell adds a comparison logic circuit to every memory cell, to provide the content-addressable functionality. Unlike RAM arrays, all data words in the word storage locations (i.e., entries) of a CAM array may be simultaneously compared with a search word (i.e., comparand) stored in a comparand buffer. This added functionality generally raises the component count in each cell by the number of transistors or other components/circuit elements needed to perform the comparison function, but adds a xe2x80x9cparallel processingxe2x80x9d characteristic to the CAM memory array. Many CAM arrays generally include a plurality of pass-transistors (e.g., PTj in FIG. 1A, where j=1, 2, . . . X) connected in parallel and connected between a Match Line and ground, to form a distributed Match Line Pass-Gate.
The CAM Match Line Pass-Gate is a distributed pass-gate comprised of the plurality of parallel Pass-Transistors or a plurality of parallel Pass-Transistor-Stacks which are connected to the Match Line. A CAM cell may comprise a pair of Pass-Transistor-Stacks that together perform a logical XNOR comparison function within the CAM cell. A Pass-Transistor-Stack may be comprised of 2 or more transistors connected in series between the Match Line and ground, forming a leg of the Match Line Pass-Gate. Each leg of the Match Line Pass-Gate may be comprised of NFETs or PFETs or a combination of these types of Field Effect Transistors (FET).
In most CAM circuits of the related art, as in FIG. 1, the Match Line functions as a capacitor having capacitance (CML) that is pre-charged (e.g., through pre-charge transistor TPC) to a logic High voltage (e.g., Vdd) prior to each search, and the observable event on each Match Line will be a MISS (the logical opposite of a MATCH which is also called a HIT), which will cause the Match Line voltage to drop (discharge towards ground voltage) from the pre-charged High voltage to a Low voltage through the Match Line Pass-Gate.
In the case of a MATCH-ing entry, the Match-Line pass-gate (i.e., comprised of all of the pass-transistor stacks connected in parallel to the Match Line) of the MATCH-ing entry will remain OFF (i.e., non-conducting). Therefore, the pre-charged Match Line of a MATCH-ing entry will remain High in the MISS-detecting CAM circuits (e.g., 102 in FIG. 1) of the related art. Thus, in the related art, the Match-sensing hardware designer is faced with the problem of detecting the lack of a Match Line voltage change, which includes challenges in defining reliable strobing protocols and sensing margins necessary to activate a reliable MATCH or HIT output signal.
In the Match Line systems of the related art, as the size (i.e., width X) of the binary word storable in each entry increases, the capacitance of each Match Line generally increases proportionately. Because the energy consumed (ECAP) by the complete discharge of a capacitor (e.g., a Match Line) is equal to xc2xdCVcap2, where C is the capacitance and Vcap is the Voltage across the capacitor, the energy consumed per search by each MISS (e.g., EMISS=ECAP) with this Match Line system can increase approximately proportionally with the increased size (X) of the word storable in the CAM entry. Additionally, the energy consumed by most of the CAM circuits of the related art is directly proportional to the frequency of searches, and therefore the Power consumed and heat generated during operation of the Miss-detecting CAM circuits (e.g., 102 of FIG. 1a) of the related art generally increases with increasing search frequency.
Although some attempt is made in the related art to minimize the energy lost upon each Miss event in each search, e.g., by minimizing the Match Line Capacitance CML, or by preventing the Match Line from completely discharging the entire pre-charged voltage (e.g., Vcap), these methods still generally fail to prevent the energy consumed in each MISS from increasing in proportion with increasing size (i.e., width X) of words in each entry and with increasing frequency of searches.
A different approach, a Match-event detection approach, is disclosed in the 1999 Japanese Patent No. JP11073783, issued to Yoshiaki, wherein each Match Line in the disclosed CAM is precharged Low (e.g., at or near ground), and raises above a Match Detection Voltage (VMD) only upon the occurrence of a MATCH of all bits in the entire entry associated with that Match Line. The Yoshiaki patent teaches that a CMOS Inverter (19) (presumably comprising a PFET transistor stacked upon an NFET transistor) driven directly and only by the Match Line voltage (VML) is to be used to detect the occurrence of a MATCH-event on the Match Line of a MATCH-ing entry, and that a HIT signal will be output from the CMOS Inverter 19 when the CMOS Inverter (19) switches in response to the Match Line voltage (VML) rising to or above the Match Detection Voltage (VMD). Consequently, the Match Detection Voltage (VMD) of Yoshiaki can not be less than the CMOS Inverter Switching Voltage (VCMOSIS) of the CMOS Inverter 19, which may equal or exceed One-Half of the Supply Voltage (VCC/2) in order to reliably register a HIT. The Match-event-detection circuit and method of Yoshiaki consumes energy (e.g., by through-currents through all MISS-ing entries) for an excessive period of time after a MATCH-event.
The explosive growth and increasing speed of Intranets and the Internet is fueling the demand for larger, faster, and more energy-efficient CAM circuits. The large CAM memory arrays of the related art-can consume multiple watts of power during performance of search operations. As the length N and entry-width X of CAM arrays continues to increase and searching becomes more frequent, the need to reduce the power consumed during CAM search operation also increases.
In designing CAMs, it is desirable that the CAM use the least energy possible when performing searches, and that each search generates a reliably detectable Match/HIT event when a MATCH-ing word is stored in an entry in the CAM. Accordingly, the present invention provides, inter alia, an improved Match-Detection Circuit and Match-detection method, for searching a Content Addressable Memory. An embodiment of the invention provides Match Detection circuitry and a method of operation that can support many known CAM storage-cell circuit topologies (e.g., Binary/Ternary/Global Masking CAM cells; SRAM/DPAM CAM cells; NFET/PFET CAM cells) while providing reduced energy consumption and other advantages over the related art.
The inventive CAM system achieves its search performance by simultaneously comparing all entries in the CAM memory with an externally applied xe2x80x9ccomparand.xe2x80x9d Words stored in the entries of the CAM array which xe2x80x9cmatchxe2x80x9d the comparand result in a Higher voltage on the Match Line and consequently the HIT line voltage (VHL) rises to a logic High voltage level, while all stored words that contain even a single bit that mis-matches (i.e., does not match) the comparand""s corresponding bit result in a Match line Low voltage (false) (and HIT Line voltage (VHL) stays Low). The Match Detection Voltage (VMD) of the present invention is the lower bound of the aforesaid xe2x80x9cHigher Match line voltage levelxe2x80x9d on the Match Line. The Match Detection Voltage (VMD) of embodiments of the invention is normally less than One Half of the Supply Voltage (i.e., less than Vcc/2).
The through-current in each MISS-ing entry is turned off completely by a carefully timed control signal at the end of the Match Detection Period and relatively soon after a MATCH-ing entry is detected or is reliably detectable. Circuits for generating the specially timed control signal to turn off the through-currents of MISS-ing entries are disclosed.
Accordingly, a first aspect of the invention provides a content addressable memory (CAM) device comprising: an entry that includes a plurality of CAM cells each coupled to a leg of a plurality of legs of a Match Line Pass-Gate and a Match Line having a Match Line Voltage, and being coupled to the Match Line Pass-Gate, such that when any legs of the Match Line Pass-Gate is conducting the Match Line is coupled to a Low voltage level; and further comprising a Match-Detection Circuit including a Field Effect Transistor (FET) coupled to the Match Line and adapted to detect a MATCH-ing entry
wherein the MATCH-ing entry is characterized by the rise of the Match Line Voltage from a Low voltage level to a Match-Detection voltage within a Match-Detection Period.
A second aspect of the invention provides an improved Match-detection circuit for a CAM entry comprising a Field Effect Transistor (FET), the gate of the Field Effect transistor being coupled to the Match Line and the FET being adapted to pull-down a node FLOAT-ing at a High voltage down towards a Low voltage when the voltage on the Match Line rises to the conducting Threshold Voltage of the FET.
A third aspect of the invention provides a digital system, such as for example, a computer, or a network router, comprising a digital processor operatively coupled to a CAM array; the CAM array having Match-detection circuits including a FET as in the forgoing aspect of the invention.